package com.example.leetcode.c201_c300.c216;
/**
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 *
 * 说明：
 *
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1:
 *
 * 输入: k = 3, n = 7
 * 输出: [[1,2,4]]
 * 示例 2:
 *
 * 输入: k = 3, n = 9
 * 输出: [[1,2,6], [1,3,5], [2,3,4]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 组合总和 III
 * @author zhanpengguo
 * @date 2020-09-11 8:08
 */
public class Solution {

    private int n;
    private int k;
    private List<List<Integer>> res = new ArrayList<>();
    private int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};

    public List<List<Integer>> combinationSum3(int k, int n) {
        this.n = n;
        this.k = k;
        hui(new ArrayList<>(), 0, 0);
        return res;
    }

    private void hui(List<Integer> list,int cur,int begin) {
        if (cur > n) {
            return;
        }
        if (list.size() > k) {
            return;
        }
        if (cur == n && list.size() == k) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = begin; i < arr.length; i++) {
            list.add(arr[i]);
            hui(list, cur + arr[i], i + 1);
            list.remove(list.size() - 1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.combinationSum3(3, 9);
        lists.forEach(System.out::println);

    }
}
